package com.wangbo.bt;

import java.util.*;

/**
 * 二叉树工具类
 */
public class BinaryTreeUtil {

    /**
     * 先序遍历，遍历实现
     */
    public static <T> void pre1(Node<T> head) {
        // 基本情形
        if (head == null) {
            return;
        }

        // 递归情形
        System.out.println(head.value);
        pre1(head.left);
        pre1(head.right);
    }

    /**
     * 先序遍历，压栈实现
     */
    public static <T> void pre2(Node<T> head) {
        System.out.print("pre-order: ");
        if (head != null) {
            Stack<Node<T>> stack = new Stack<>();
            stack.push(head);
            while (!stack.isEmpty()) {
                /**
                 * 弹出就打印，如有右压入右，如有左压入左，先右再左。
                 */
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历，递归实现
     */
    public static <T> void in1(Node<T> head) {
        // 基本情形
        if (head == null) {
            return;
        }

        // 递归情形
        pre1(head.left);
        System.out.println(head.value);
        pre1(head.right);
    }

    /**
     * 中序遍历，压栈实现
     */
    public static <T> void in2(Node<T> head) {
        System.out.print("in-order: ");
        if (head != null) {
            Stack<Node<T>> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

    /**
     * 后序遍历，递归实现
     */
    public static <T> void pos1(Node<T> root) {
        // 基本情形
        if (root == null) {
            return;
        }

        // 递归情形
        pre1(root.left);
        pre1(root.right);
        System.out.println(root.value);
    }

    /**
     * 后序遍历，压栈实现
     */
    public static <T> void pos2(Node<T> head) {
        System.out.print("pos-order: ");
        if (head != null) {
            Stack<Node<T>> stack = new Stack<>();
            stack.push(head);
            Node<T> top = null;
            while (!stack.isEmpty()) {
                top = stack.peek();
                if (top.left != null && head != top.left && head != top.right) {
                    stack.push(top.left);
                } else if (top.right != null && head != top.right) {
                    stack.push(top.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    head = top;
                }
            }
        }
        System.out.println();
    }

    /**
     * 广度优先遍历 (队列实现)
     * 原理：上一层出队的同时，实现下一层的入队，上一层出队完成，意味着下一层入队完成。
     */
    public static <T> void broadTraverse(Node<T> head) {
        Queue<Node<T>> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            Node<T> node = queue.poll();

            System.out.print(head.value + " -> ");

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    /**
     * 统计树的层级和最大宽度
     */
    public static <T> Map<String,Integer> getMetaData(Node<T> head) {
        if (head == null) {
            return null;
        }

        Queue<Node<T>> queue = new LinkedList<>();
        queue.add(head);
        queue.add(null); // 第一层结束符
        int max = 0; // 最大宽度
        int count = 0; // 宽度计数器
        int level = 0; // 层级计数器
        while (!queue.isEmpty()) {
            Node<T> node = queue.poll();

            if (node != null) { // 上层出队遍历
                count++;
                // 下层入队
                if (node.left != null) { // null是层结束符，具有特殊含义，所以必须加非空判断，防止空节点入队
                    queue.add(node.left);
                }
                if (node.right != null) { // null是层结束符，具有特殊含义，所以必须加非空判断，防止空节点入队
                    queue.add(node.right);
                }
            } else { // 上层遍历结束
                max = max >= count ? max : count;
                level++;
                count = 0;
                if (!queue.isEmpty()) { // 如果队列不为空，说明下层存在，并且下层节点已全部入队，添加结束符null
                    queue.add(null);
                }
            }
        }

        HashMap<String, Integer> map = new HashMap<>();
        map.put("width", max);
        map.put("level", level);
        return map;
    }

    /**
     * 二叉树序列化，递归实现，先序
     */
    public static <T> void preSerialize(Node<T> head, Queue<T> queue) {
        if (head == null) {
            queue.add(null); // 用null占位
        } else {
            queue.add(head.value);
            preSerialize(head.left, queue);
            preSerialize(head.right, queue);
        }
    }

    /**
     * 二叉树反序列化，递归实现，先序
     */
    public static <T> Node<T> preDeserialize(Queue<T> queue) {
        T value = queue.poll();
        if (value == null) {
            return null;
        }
        Node<T> head = new Node<>(value);
        head.left = preDeserialize(queue);
        head.right = preDeserialize(queue);
        return head;
    }

    /**
     * 二叉树序列化，广度优先遍历实现
     */
    public static <T> void levelSerialize(Node<T> head, Queue<T> queue) {
        if (head == null) {
            queue.add(null); // 用null占位
        } else {
            Queue<Node<T>> help = new LinkedList<>(); // 辅助按层遍历
            help.add(head);
            queue.add(head.value);
            while (!help.isEmpty()) {
                // 上层出队
                head = help.poll();

                // 下层入队
                if (head.left != null) {
                    help.add(head.left);
                    queue.add(head.left.value);
                } else {
                    queue.add(null); // 用null占位
                }
                if (head.right != null) {
                    queue.add(head.right.value);
                    help.add(head.right);
                } else {
                    queue.add(null); // 用null占位
                }
            }
        }
    }

    /**
     * 二叉树反序列化，广度优先遍历实现
     */
    public static <T> Node<T> levelDeserialize(Queue<T> queue) {
        if (queue == null || queue.isEmpty()) {
            return null;
        }
        Node<T> head = generateNode(queue.poll());
        Queue<Node<T>> help = new LinkedList<>(); // 辅助按层遍历
        if (head != null) {
            help.add(head);
        }
        Node<T> node = null;
        while (!help.isEmpty()) {
            // 上层出队
            node = help.poll();

            // 下层入队
            node.left = generateNode(queue.poll());
            node.right = generateNode(queue.poll());
            if (node.left != null) {
                help.add(node.left);
            }
            if (node.right != null) {
                help.add(node.right);
            }
        }

        return head;
    }

    public static <T> Node<T> generateNode(T value) {
        if (value == null) {
            return null;
        }
        return new Node<>(value);
    }

}
